package zijie;

import java.util.List;

/**
 * 148. 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class SortList_148_26 {

    public ListNode sortList(ListNode head) {
        return sort(head, null);
    }

    public ListNode sort(ListNode head,ListNode tail){
        if(head == null){
            return null;
        }
        if(head.next == tail){
            head.next = null;
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail && fast.next != tail){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow;
        ListNode left = sort(head,mid);
        ListNode right = sort(mid,tail);
        return merge(left,right);
    }

    private ListNode merge(ListNode left, ListNode right){
        ListNode mergeNode = new ListNode();
        ListNode helper = mergeNode;
        while(left != null && right != null){
            if(left.val < right.val){
                helper.next = left;
                left = left.next;
            }else{
                helper.next  = right;
                right = right.next;
            }
            helper = helper.next;
        }
        helper.next = left == null ? right:left;
        return mergeNode.next;
    }



    public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

}
